package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;

import cn.edu.jxau.util.LinkedQueue;
import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Queue;
import cn.edu.jxau.util.Stack;

/**
 * 已二叉查找树为基础，实现二叉树的各种操作
 * 
 * http://www.61mon.com/index.php/archives/191/
 * http://www.cnblogs.com/keedor/p/4467040.html
 * http://www.jianshu.com/p/0190985635eb
 * http://www.cnblogs.com/Jax/archive/2009/12/28/1633691.html
 * http://www.cnblogs.com/cyttina/archive/2012/10/26/2741811.html
 * http://blog.csdn.net/u012605629/article/details/40429125
 * 
 * @author 付大石
 */
public class BinarySearchTree<T extends Comparable<T>> {

    public static void main(String[] args) {

//        BinarySearchTree<Integer> bst = new BinarySearchTree(new Integer[] { 23, 54, 45, 34, 76, 12, 98 });
//        BinarySearchTree<Integer> bst = new BinarySearchTree(new Integer[] { 1, 2, 3, 4, 5, 6, 7 });
//        for (Integer i : bst.preOrder()) {
//            System.out.print(i + " ");
//        }
//        System.out.println();
//        for (Integer i : bst.inOrder()) {
//            System.out.print(i + " ");
//        }
//        System.out.println();
//        System.out.println(bst.isBST());
//        System.out.println(bst.isBT());

        System.out.println(isPostOrderOfBST(new int[] {7,11,16,20,52,51,50,18}));
    }

    /**
     * 二叉查找树的根节点
     */
    private Node root;

    /**
     * 二叉查找树的节点数
     */
    private int size;

    public BinarySearchTree() {

    }

    public BinarySearchTree(T data) {

        Objects.requireNonNull(data, "参数data不能为null");
        this.root = new Node(data);
        this.size = 1;
    }

    /**
     * 用一个数组（不要求顺序）构造二叉查找树
     * 
     * @param arr
     */
//    public BinarySearchTree(T[] arr) {
//
//        Objects.requireNonNull(arr, "参数arr不能为null");
//        for (T data : arr) {
//            insert(data);
//        }
//    }

    /**
     * 使用升序数组构造出一个平衡的二叉树（但并不符合二叉查找树的性质）
     * 
     * @param arr
     */
//    public BinarySearchTree(T[] arr) {
//        root = insert(arr, 0, root);
//    }
//
//    private Node insert(T[] arr, int pos, Node node) {
//
//        node = new Node();
//        node.data = arr[pos];
//        if (pos * 2 + 1 <= arr.length - 1) {
//            node.left = insert(arr, pos * 2 + 1, node.left);
//        }
//        if (pos * 2 + 2 <= arr.length - 1) {
//            node.right = insert(arr, pos * 2 + 2, node.right);
//        }
//        return node;
//    }

    /**
     * 使用升序数组构造出一个平衡的二叉树（符合二叉查找树的性质）
     * 
     * @param arr
     */
    public BinarySearchTree(T[] arr) {
        root = buildTree(arr, 0, arr.length - 1);
    }

    private Node buildTree(T[] arr, int low, int high) {

        if (high < low) {
            return null;
        }
        int mid = low + ((high - low) >> 1);
        Node node = new Node(arr[mid]);
        node.left = buildTree(arr, low, mid - 1);
        node.right = buildTree(arr, mid + 1, high);
        return node;
    }

    public boolean contains(T data) {

        Objects.requireNonNull(data, "参数data不能为null");
        Node current = root;
        while (current != null) {
            int cmp = current.data.compareTo(data);
            if (cmp > 0) {
                current = current.left;
            } else if (cmp < 0) {
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 向二叉查找树中插入一个data结点
     *
     * @param data
     */
    public void insert(T data) {

        // 参数校验 //
        Objects.requireNonNull(data);

        // 特殊情况处理 //
        if (root == null) {
            root = new Node(data);
            size++;
            return;
        }

        // 插入一个结点 //
        Node parent = null;
        Node current = root;
        while (current != null) {
            int cmp = current.data.compareTo(data);
            if (cmp > 0) {
                parent = current;
                current = current.left;
            } else if (cmp < 0) {
                parent = current;
                current = current.right;
            } else { // data结点已存在
                return;
            }
        }
        int cmp = parent.data.compareTo(data);
        if (cmp > 0) {
            parent.left = new Node(data);
        } else if (cmp < 0) {
            parent.right = new Node(data);
        }
        size++;
    }

//    public int size() {
//        return size;
//    }

    /**
     * 使用递归计算二叉树的结点数
     * 
     * @return
     */
    public int size() {
        return size(root);
    }

    private int size(Node node) {

        if (node == null) {
            return 0;
        }
        return size(node.left) + size(node.right) + 1;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void delete(T data) {

        // 参数校验 //
        if (isEmpty()) {
            throw new RuntimeException("这是棵空树");
        }

        // 找到要删除的结点 //
        Node parent = null;
        Node current = root;
        while (current != null) {
            int cmp = current.data.compareTo(data);
            if (cmp > 0) {
                parent = current;
                current = current.left;
            } else if (cmp < 0) {
                parent = current;
                current = current.right;
            } else { // 成功找到结点
                break;
            }
        }
        if (current == null) { // 未找到结点
            return;
        }
        if (parent == null) { // 要删除根节点
            if (root.left != null && root.right != null) { // 左右子树均不为空
                Node min = minNode(root.right);
                min.right = deleteMin(root.right);
                min.left = root.left;
                root = min;
            } else if (root.left != null && root.right == null) { // 左子树不为空，右子树为空
                root = root.left;
            } else if (root.right != null && root.left == null) { // 右子树不为空，左子树为空
                root = root.right;
            } else { // 左右子树均为空
                root = null;
            }
            return;
        }
        int cmp = parent.data.compareTo(current.data); // 判断current是parent的左孩子还是parent的右孩子
        if (cmp > 0) { // current是parent的左孩子
            if (current.left != null && current.right != null) { // 左右子树均不为空
                Node min = minNode(current.right);
                min.right = deleteMin(current.right);
                min.left = current.left;
                parent.left = min;
            } else if (current.left != null && current.right == null) { // 左子树不为空，右子树为空
                parent.left = current.left;
            } else if (current.right != null && current.left == null) { // 右子树不为空，左子树为空
                parent.left = current.right;
            } else { // 左右子树均为空
                parent.left = null;
            }
        } else if (cmp < 0) { // current是parent的右孩子
            if (current.left != null && current.right != null) {
                Node min = minNode(current.right);
                min.right = deleteMin(current.right);
                min.left = current.left;
                parent.right = min;
            } else if (current.left != null && current.right == null) {
                parent.right = current.left;
            } else if (current.right != null && current.left == null) {
                parent.right = current.right;
            } else { // 左右子树均为空
                parent.right = null;
            }
        } else {
            // never go to here
        }
    }

    private Node minNode(Node node) {
        if (node.left == null) {
            return node;
        }
        return minNode(node.left);
    }

    private Node deleteMin(Node node) {

        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }

    /**
     * 结点类
     * 
     * @author 付大石
     */
    private class Node {

        private T data;
        private Node left;
        private Node right;

        public Node(T data) {
            this.data = data;
        }

        public Node() {

        }
    }

    // -------------------------------------------------------
    // 各种二叉树操作
    // -------------------------------------------------------

    /**
     * 计算二叉树的叶子节点数量
     * 
     * @return
     */
    public int countLeaves() {
        return countLeaves(root);
    }

    private int countLeaves(Node node) {

        if (node == null) {
            return 0;
        }
        if (node.left == null || node.right == null) {
            return 1;
        }
        return countLeaves(node.left) + countLeaves(node.right);
    }

    /**
     * 计算二叉树中，第k层的节点数，k从1开始
     * 
     * @param k
     * @return
     */
    public int getKSize(int k) {

        if (k <= 0) {
            throw new IllegalArgumentException("参数异常，k必须为正数");
        }
        return getKSize(root, k);
    }

    public int getKSize(Node node, int k) {

        if (node == null)
            return 0;
        if (k == 1)
            return 1;
        return getKSize(node.left, k - 1) + getKSize(node.right, k - 1);
    }

    /**
     * 找出二叉树从根节点到叶子节点所经过的所有节点值其和为sum的组合
     * 仅限Integer类型
     * 
     * @param sum
     */
    public void sum(int sum) {
        sum(root, sum, new LinkedStack<>());
    }

    private void sum(Node node, int sum, Stack<Integer> stack) {

        if (node == null) {
            return;
        }
        stack.push((Integer) node.data);
        if (node.left == null && node.right == null) { // 叶子结点

            if (((Integer) node.data).compareTo(sum) == 0) {
                Stack<Integer> reverse = new LinkedStack<>(); // 逆序输出stack中的数据
                while (!stack.isEmpty()) {
                    reverse.push(stack.pop());
                }
                while (!reverse.isEmpty()) {
                    System.out.print(reverse.peek() + " ");
                    stack.push(reverse.pop());
                }
                System.out.println();
            }
        }
        sum(node.left, sum - ((Integer) node.data), stack);
        sum(node.right, sum - ((Integer) node.data), stack);
        stack.pop();
    }

    /**
     * 比较两棵树在结构上和内容上是否相同
     * 
     * @param bst
     * @return
     */
    @Override
    public boolean equals(Object bst) {
        if (this == bst) { // 自反性
            return true;
        }
        if (bst instanceof BinarySearchTree) {
            return equals(root, ((BinarySearchTree) bst).root);
        }
        return false;
    }

    private boolean equals(Node node1, Node node2) {

        if (node1 == null && node2 == null) {
            return true;
        } else if (node1 != null && node2 != null) {
            System.out.println(node1.data + " " + node2.data);
            if (node1.data.compareTo(node2.data) != 0) { // 内容比较
                return false;
            }
            return equals(node1.left, node2.left) && equals(node1.right, node2.right);
        } else { // node1和node2两者之间有一个为null，结构不同，返回false
            return false;
        }
    }

    /**
     * 忽略二叉树中的内容，比较两棵树在结构上是否相同
     * 
     * @param bst
     * @return
     */
    public boolean equalsIgnoreContent(BinarySearchTree bst) {

        Objects.requireNonNull(bst, "参数bst不能为null");
        return equalsIgnoreContent(root, bst.root);
    }

    private boolean equalsIgnoreContent(Node node1, Node node2) {

        if (node1 == null && node2 == null) {
            return true;
        } else if (node1 != null && node2 != null) {
            return equalsIgnoreContent(node1.left, node2.left) && equalsIgnoreContent(node1.right, node2.right);
        } else { // node1和node2两者之间有一个为null，结构不同，返回false
            return false;
        }
    }

    public void mirror() {
        mirror(root);
    }

    private void mirror(Node node) {

        if (node == null) {
            return;
        }
        Node temp = node.left;
        node.left = node.right;
        node.right = temp;
        mirror(node.left);
        mirror(node.right);
    }

    /**
     * 判断两个二叉树是否互为镜像
     * 
     * @param tree
     * @return
     */
    public boolean isMirror(BinarySearchTree<T> tree) {
        return isMirror(root, tree.root);
    }

    private boolean isMirror(Node node1, Node node2) {

        if (node1 == null && node2 == null) {
            return true;
        }

        if (node1 == null || node2 == null) {
            return false;
        }

        if (node1.data.compareTo(node2.data) == 0) {
            return true;
        }
        return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);

    }

    /**
     * 获取data节点的父节点
     * 
     * @param data
     * @return
     */
    public T getParent(T data) {

        Objects.requireNonNull(data, "参数data不能为null");
        Node node = getNode(data);
        Objects.requireNonNull(node, "data不存在于该二叉树中");
        Node p = getParent(root, node);
        return p == null ? null : p.data;
    }

    public Node getParent(Node node, Node target) {

        if (target == null) {
            return null;
        }
        if (node == null) {
            return null;
        }
        if (node.left == target || node.right == target) {
            return node;
        }
        Node parent = getParent(node.left, target);
        if (parent == null) {
            parent = getParent(node.right, target);
        }
        return parent;
    }

    /**
     * 获取树的深度
     * 
     * @return
     */
    public int getDepth() {
        return getDepth(root);
    }

    public int getDepth(Node node) {

        if (node == null) {
            return 0;
        }
        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);
        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }

    /**
     * 前序遍历
     * 
     * @return
     */
    public Iterable<T> preOrder() {

        List<T> list = new ArrayList<>();
        preOrder(root, list);
        return list;
    }

    private void preOrder(Node node, List<T> list) {

        if (node == null) {
            return;
        }
        list.add(node.data);
        preOrder(node.left, list);
        preOrder(node.right, list);
    }

    /**
     * 非递归的前序遍历
     * 
     * @return
     */
//    public Iterable<T> preOrderWithStack() {
//
//        if (isEmpty()) {
//            return Collections.emptyList();
//        }
//        List<T> list = new ArrayList<>();
//        Stack<Node> stack = new LinkedStack<>();
//        Node current = root;
//        while (current != null || !stack.isEmpty()) {
//            while (current != null) {
//                list.add(current.data);
//                stack.push(current);
//                current = current.left;
//            }
//            if (!stack.isEmpty()) {
//                current = stack.peek().right;
//                stack.pop();
//            }
//        }
//        return list;
//    }

    /**
     * 非递归的前序遍历
     * 
     * @return
     */
    public Iterable<T> preOrderWithStack() {

        if (isEmpty()) {
            return Collections.emptyList();
        }
        List<T> list = new ArrayList<>();
        Stack<Node> stack = new LinkedStack<>();
        stack.push(root);
        while (!stack.isEmpty()) {

            Node node = stack.pop();
            list.add(node.data);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return list;
    }

    /**
     * 中序遍历
     * 
     * @return
     */
    public Iterable<T> inOrder() {

        List<T> list = new ArrayList<>();
        inOrder(root, list);
        return list;
    }

    private void inOrder(Node node, List<T> list) {

        if (node == null) {
            return;
        }
        inOrder(node.left, list);
        list.add(node.data);
        inOrder(node.right, list);
    }

    /**
     * 非递归的中序遍历
     * 
     * @return
     */
    public Iterable<T> inOrderWithStack() {

        if (isEmpty()) {
            return Collections.emptyList();
        }
        List<T> list = new ArrayList<>();
        Stack<Node> stack = new LinkedStack<>();
        Node current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            if (!stack.isEmpty()) {
                list.add(stack.peek().data);
                current = stack.peek().right;
                stack.pop();
            }
        }
        return list;
    }

    /**
     * 后序遍历
     * 
     * @return
     */
    public Iterable<T> postOrder() {

        List<T> list = new ArrayList<>();
        postOrder(root, list);
        return list;
    }

    private void postOrder(Node node, List<T> list) {

        if (node == null) {
            return;
        }
        postOrder(node.left, list);
        postOrder(node.right, list);
        list.add(node.data);
    }

    /**
     * 非递归的后序遍历
     * 
     * @return
     */
    public Iterable<T> postOrderWithStack() {

        if (isEmpty()) {
            return Collections.emptyList();
        }
        List<T> list = new ArrayList<>();
        Stack<Node> stack = new LinkedStack<>();
        Node current = root;
        Node pre = null;
        stack.push(current);
        while (!stack.isEmpty()) {
            current = stack.peek();
            if ((current.left == null && current.right == null) || // 第一个节点必是叶子节点
                    (pre != null && (pre == current.left || pre == current.right))) { // 往后的节点的pre就不会为null
                list.add(current.data);
                pre = current;
                stack.pop();
            } else { // 先进右孩子再进左孩子
                if (current.right != null) {
                    stack.push(current.right);
                }
                if (current.left != null) {
                    stack.push(current.left);
                }
            }
        }
        return list;
    }

    /**
     * 层次遍历(实质上就是从根节点出发的广度优先)
     * 
     * @return
     */
//    public Iterable<T> levelOrder() {
//        return levelOrder(root);
//    }
//
//    private Iterable<T> levelOrder(Node node) {
//
//        List<T> list = new ArrayList<>();
//        Queue<Node> queue = new LinkedQueue<>();
//        queue.enqueue(node);
//        while (!queue.isEmpty()) {
//            Node temp = queue.dequeue();
//            list.add(temp.data);
//            if (temp.left != null) {
//                queue.enqueue(temp.left);
//            }
//            if (temp.right != null) {
//                queue.enqueue(temp.right);
//            }
//        }
//        return list;
//    }

    /**
     * 使用链表层次遍历一棵二叉树
     * @return
     */
    public Iterable<T> levelOrder() {

        List<T> list = new ArrayList<>();
        levelOrder(root, list);
        return list;
    }

    private void levelOrder(Node node, List<T> list) {

        if (node == null) {
            return;
        }

        LinkedNode first = new LinkedNode();
        first.data = node;
        LinkedNode second = first;
        while (first != null) {

            if (first.data.left != null) {
                second.next = new LinkedNode(first.data.left);
                second = second.next;
            }
            if (first.data.right != null) {
                second.next = new LinkedNode(first.data.right);
                second = second.next;
            }
            list.add(first.data.data);
            System.out.println(first.next);
            first = first.next;
        }
    }

    private class LinkedNode {

        private Node data;
        private LinkedNode next;

        public LinkedNode(Node data) {
            this.data = data;
        }

        public LinkedNode() {

        }
    }

    /**
     * 从根节点到data所经过的结点
     * 
     * @param data
     * @return
     */
    public Iterable<T> getPath(T data) {

        if (isEmpty()) {
            throw new RuntimeException("这是棵空树");
        }
        List<T> list = new ArrayList<>();
        Node current = root;
        while (current != null) {
            int cmp = current.data.compareTo(data);
            list.add(current.data);
            if (cmp > 0) {
                current = current.left;
            } else if (cmp < 0) {
                current = current.right;
            } else {
                return list;
            }
        }
        return Collections.emptyList();
    }

    /**
     * 求两个节点的最低公共祖先节点
     * find lowest common ancestor
     * 
     * @param data1
     * @param data2
     * @return
     */
    public T getLCA(T data1, T data2) {

        // 参数校验 //
        Objects.requireNonNull(data1, "data1不能为空");
        Objects.requireNonNull(data2, "data2不能为空");

        // 分别获取data1、data2代表的结点 //
        Node node1 = getNode(data1);
        Node node2 = getNode(data2);
        Objects.requireNonNull(node1, "data1不存在于二叉树中");
        Objects.requireNonNull(node2, "data2不存在于二叉树中");

        Node node = getLCA(root, node1, node2);
        return node != null ? node.data : null;
    }

//    private Node getLCA(Node node, Node target1, Node target2) {
//
//        if (node == null) {
//            return null;
//        }
//        if (node == target1 || node == target2) {
//            return node;
//        }
//        Node left = getLCA(node.left, target1, target2);
//        Node right = getLCA(node.right, target1, target2);
//        if (left != null && right != null) {
//            return node;
//        }
//        return left != null ? left : right; // 返回left、right中不会空的一个
//    }

    /**
     * 没有考虑到target1、target2在一个分支上的情况
     * 
     * @param node
     * @param target1
     * @param target2
     * @return
     */
//    private Node getLCA(Node node, Node target1, Node target2) {
//
//        if (contains(node.left, target1)) {
//            if (contains(node.right, target2)) {
//                return node;
//            } else {
//                return getLCA(node.left, target1, target2);
//            }
//        } else if (contains(node.right, target1)) {
//            if (contains(node.left, target2)) {
//                return node;
//            } else {
//                return getLCA(node.right, target1, target2);
//            }
//        }
//        return null;
//    }

    private Node getLCA(Node node, Node target1, Node target2) {

        Stack<Node> s1 = new LinkedStack<>();
        traverse(root, target1, s1);
        Stack<Node> s2 = new LinkedStack<>();
        traverse(root, target2, s2);
        Node result = null;
        while (s1.peek() == s2.peek()) {
            result = s1.pop();
            s2.pop();
        }
        return result;
    }

    /**
     * 记录node到target遍历的节点，记录用的容器是stack
     * 
     * @param node
     * @param target
     * @param stack
     * @return
     */
    private boolean traverse(Node node, Node target, Stack<Node> stack) {

        if (node == null) {
            return false;
        }
        if (node == target) {
            stack.push(node);
            return true;
        }
        if (traverse(node.left, target, stack) || traverse(node.right, target, stack)) {
            stack.push(node);
            return true;
        }
        return false;
    }

    /**
     * 判断以node节点为根节点的二叉树是否包含target节点
     * @param node
     * @param target
     * @return
     */
    private boolean contains(Node node, Node target) {

        if (node == null || target == null) {
            return false;
        }
        if (node == target) {
            return true;
        }
        boolean contains = contains(node.left, target);
        if (!contains) {
            contains(node.right, target);
        }
        return contains;
    }

    private Node getNode(T data) {
        return getNode(root, data);
    }

    private Node getNode(Node node, T data) {

        if (node == null) {
            return null;
        }

        int cmp = node.data.compareTo(data);
        if (cmp > 0) {
            return getNode(node.left, data);
        } else if (cmp < 0) {
            return getNode(node.right, data);
        } else {
            return node;
        }
    }

    /**
     * 求任意两节点距离
     * 
     * @param data1
     * @param data2
     * @return
     */
    public int getDistance(T data1, T data2) {

        // 参数校验 //
        Objects.requireNonNull(data1, "data1不能为空");
        Objects.requireNonNull(data2, "data2不能为空");

        // 分别获取data1、data2代表的结点 //
        Node node1 = getNode(data1);
        Node node2 = getNode(data2);
        Objects.requireNonNull(node1, "data1不存在于二叉树中");
        Objects.requireNonNull(node2, "data2不存在于二叉树中");
        Node lca = getLCA(root, node1, node2);
        return getDistance(lca, node1) + getDistance(lca, node2);
    }

    /**
     * 获取node结点到target结点的距离(node结点到target结点的链接数)
     * 
     * @param node
     * @param target
     * @return
     */
    private int getDistance(Node node, Node target) {

        if (node == null) {
            return -1;
        }
        if (node == target) {
            return 0;
        }
        int distance = getDistance(node.left, target); // 先去左子树找
        if (distance == -1) {
            distance = getDistance(node.right, target); // 找不着则去右子树找
        }
        if (distance != -1) {
            return distance + 1; // 回溯
        }
        return -1;
    }

    public Iterable<T> traverseAncestors(T data) {

        // 参数校验 //
        Objects.requireNonNull(data, "data1不能为空");

        // 获取data代表的结点 //
        Node node = getNode(data);
        Objects.requireNonNull(node, "data不存在于二叉树中");
        List<T> list = new ArrayList<>();
        traverseAncestors(root, node, list);
        return list;
    }

    private boolean traverseAncestors(Node node, Node target, List<T> list) {

        if (node == null) {
            return false;
        }
        if (node == target) {
            return true;
        }
        if (traverseAncestors(node.left, target, list) || traverseAncestors(node.right, target, list)) {
            list.add(node.data);
            return true;
        } else {
            return false;
        }
    }

    /**
     * is compelete binary tree,判断是否是完全二叉树
     * 实质是个广度优先遍历
     * 
     * @return
     */
    public boolean isCBT() {

        if (isEmpty()) { // 空树也是完全二叉树
            return true;
        }

        boolean flag = false; // 判断是否到了最后缺的那一部分
        Queue<Node> queue = new LinkedQueue<>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node node = queue.dequeue();
            if (flag) {
                if (node.left != null || node.right != null) {
                    return false;
                }
            } else {
                if (node.left != null && node.right != null) { // 左右子树都不为空
                    queue.enqueue(node.left);
                    queue.enqueue(node.right);
                } else if (node.left != null && node.right == null) { // 左不空右空，遍历到了最后一部分
                    queue.enqueue(node.left);
                    flag = true;
                } else if (node.right != null && node.left == null) { // 左空右不空，肯定不是完全二叉树
                    return false;
                } else { // 左右子树都为空
                    return true;
                }

            }
        }
        return true;
    }

    /**
     * is balance tree 判断二叉树是否是平衡二叉树
     * @return
     */
    public boolean isBT() {

        return isBT(root);
    }

    private boolean isBT(Node node) {

        if (node == null) {
            return true;
        }
        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return false;
        }
        return isBT(node.left) && isBT(node.right);
    }

    /**
     * is binary search tree，判断是否是二叉查找树
     * 理由二叉查找树的中序遍历是有序的性质
     * 
     * @return
     */
//    public boolean isBST() {
//
//        Iterator<T> iterator = inOrder().iterator();
//        T pre = iterator.next();
//        T post = null;
//        while (iterator.hasNext()) {
//            post = iterator.next();
//            if (post.compareTo(pre) < 0) {
//                return false;
//            }
//            pre = post;
//        }
//        return true;
//    }

    public boolean isBST() {
        return isBST(root, minNode(root).data);
    }

    private boolean isBST(Node node, T pre) {

        if (node == null) {
            return true;
        }
        if (!isBST(node.left, pre)) {
            return false;
        }
        if (node.data.compareTo(pre) < 0) { // 当前节点比中序遍历的前一个节点小
            return false;
        }
        pre = node.data;
        if (!isBST(node.right, pre)) {
            return false;
        }
        return true;
    }

    /**
     * 将二叉查找树转化成有序的链表
     */
    public void toSortedList() {

        if (!isBST()) {
            throw new IllegalStateException("该二叉树不是二叉查找树");
        }
        Node head = null;
        Node pre = null; // 前驱指针
        head = toSortedList(root, null);
        // 顺序、逆序遍历链表 //
        Node cursor = head;
        while (cursor != null) {
            System.out.print(cursor.data + " ");
            cursor = cursor.right;
        }
//        System.out.println();
//        cursor = last;
//        while (cursor != null) {
//            System.out.print(cursor.data + " ");
//            cursor = cursor.left;
//        }
    }

    /**
     * 返回的节点是list的最后的节点
     * @param node
     * @param last
     * @return
     */
//    private Node toSortedList(Node node, Node last) {
//
//        if (node == null) {
//            return last;
//        }
//        if (node.left != null) {
//            last = toSortedList(node.left, last);
//        }
//        node.left = last;
//        if(last != null) {
//            last.right = node;
//        }
//        last = node;
//        if(node.right != null) {
//            last = toSortedList(node.right, last);
//        }
//        return last;
//    }

    /**
     * 返回的节点是list的开始的节点
     * @param node
     * @param last
     * @return
     */
    private Node toSortedList(Node node, Node first) {

        if (node == null) {
            return first;
        }
        if (node.right != null) {
            first = toSortedList(node.right, first);
        }
        node.right = first;
        if (first != null) {
            first.left = node;
        }
        first = node;
        if (node.left != null) {
            first = toSortedList(node.left, first);
        }
        return first;
    }

    /**
     * 判断所给的{@code postOrder}是否是某棵二叉查找树的后序遍历结果
     * @param postOrder
     * @return
     */
    public static boolean isPostOrderOfBST(int[] postOrder) {
        return isPostOrderOfBST(postOrder, 0, postOrder.length - 1);
    }

    private static boolean isPostOrderOfBST(int[] postOrder, int low, int high) {

        if (low >= high) {
            return true;
        }
        int split = 0; // 分隔左子树和右子树
        int i = low;
        for (; i < high; i++) {
            if (postOrder[i] > postOrder[high]) { // 已经遍历到右子树
                split = i;
                break;
            }
        }
        for (; i < high; i++) { // 遍历右子数，查看是否有比根节点postOrder[high]小的元素
            if (postOrder[i] < postOrder[high]) {
                return false;
            }
        }
        return isPostOrderOfBST(postOrder, low, split - 1) && isPostOrderOfBST(postOrder, split, high - 1);
    }
}